package mo.offer_special;

import java.util.Random;

public class L071 {

    private int[] pre;
    private int sum;
    private Random random;

    public L071(int[] w) {
        random = new Random();
        pre = new int[w.length];
        pre[0] = w[0];
        for (int i = 1; i < w.length; i++) {
            pre[i] = pre[i-1] + w[i];
        }
        sum = pre[w.length-1];
    }

    public int pickIndex() {
        int x = random.nextInt(sum) + 1;
        int left = 0;
        int right = pre.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (pre[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }


}
